Runtime Complexity (full) proof of /tmp/tmpfim9Po/cime3.xml

The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(2^n, INF).

0 CpxTRS

↳1 DecreasingLoopProof (⇔, 591 ms)

↳2 BOUNDS(2^n, INF)

↳3 RenamingProof (⇔, 0 ms)

↳4 CpxRelTRS

    ↳5 TypeInferenceProof (BOTH BOUNDS(ID, ID), 0 ms)

    ↳6 typed CpxTrs

    ↳7 OrderProof (LOWER BOUND(ID), 0 ms)

    ↳8 typed CpxTrs

    ↳9 NoRewriteLemmaProof (LOWER BOUND(ID), 38.4 s)

    ↳10 typed CpxTrs

    ↳11 NoRewriteLemmaProof (LOWER BOUND(ID), 0 ms)

    ↳12 typed CpxTrs

    ↳13 NoRewriteLemmaProof (LOWER BOUND(ID), 509 ms)

    ↳14 typed CpxTrs

    ↳15 NoRewriteLemmaProof (LOWER BOUND(ID), 38.1 s)

    ↳16 typed CpxTrs

    ↳17 NoRewriteLemmaProof (LOWER BOUND(ID), 9145 ms)

    ↳18 typed CpxTrs

    ↳19 RewriteLemmaProof (LOWER BOUND(ID), 2848 ms)

    ↳20 BEST

        ↳21 typed CpxTrs

            ↳22 NoRewriteLemmaProof (LOWER BOUND(ID), 0 ms)

            ↳23 typed CpxTrs

            ↳24 NoRewriteLemmaProof (LOWER BOUND(ID), 0 ms)

            ↳25 typed CpxTrs

            ↳26 NoRewriteLemmaProof (LOWER BOUND(ID), 0 ms)

            ↳27 typed CpxTrs

            ↳28 NoRewriteLemmaProof (LOWER BOUND(ID), 0 ms)

            ↳29 typed CpxTrs

            ↳30 NoRewriteLemmaProof (LOWER BOUND(ID), 0 ms)

            ↳31 typed CpxTrs

            ↳32 LowerBoundsProof (⇔, 0 ms)

            ↳33 BOUNDS(n^1, INF)

        ↳34 typed CpxTrs

            ↳35 LowerBoundsProof (⇔, 0 ms)

            ↳36 BOUNDS(n^1, INF)

(0) Obligation:

Runtime Complexity TRS:
The TRS R consists of the following rules:

a__a → a__c
a__b → a__c
a__c → e
a__k → l
a__d → m
a__a → a__d
a__b → a__d
a__c → l
a__k → m
a__A → a__h(a__f(a__a), a__f(a__b))
a__h(X, X) → a__g(mark(X), mark(X), a__f(a__k))
a__g(d, X, X) → a__A
a__f(X) → a__z(mark(X), X)
a__z(e, X) → mark(X)
mark(A) → a__A
mark(a) → a__a
mark(b) → a__b
mark(c) → a__c
mark(d) → a__d
mark(k) → a__k
mark(z(X1, X2)) → a__z(mark(X1), X2)
mark(f(X)) → a__f(mark(X))
mark(h(X1, X2)) → a__h(mark(X1), mark(X2))
mark(g(X1, X2, X3)) → a__g(mark(X1), mark(X2), mark(X3))
mark(e) → e
mark(l) → l
mark(m) → m
a__A → A
a__a → a
a__b → b
a__c → c
a__d → d
a__k → k
a__z(X1, X2) → z(X1, X2)
a__f(X) → f(X)
a__h(X1, X2) → h(X1, X2)
a__g(X1, X2, X3) → g(X1, X2, X3)

Rewrite Strategy: FULL

(1) DecreasingLoopProof (EQUIVALENT transformation)

The following loop(s) give(s) rise to the lower bound Ω(2ⁿ):
The rewrite sequence
mark(z(f(X35587_0), X2)) →⁺ a__z(a__z(mark(mark(X35587_0)), mark(X35587_0)), X2)
gives rise to a decreasing loop by considering the right hand sides subterm at position [0,0,0].
The pumping substitution is [X35587_0 / z(f(X35587_0), X2)].
The result substitution is [ ].

The rewrite sequence
mark(z(f(X35587_0), X2)) →⁺ a__z(a__z(mark(mark(X35587_0)), mark(X35587_0)), X2)
gives rise to a decreasing loop by considering the right hand sides subterm at position [0,1].
The pumping substitution is [X35587_0 / z(f(X35587_0), X2)].
The result substitution is [ ].

(2) BOUNDS(2^n, INF)

(3) RenamingProof (EQUIVALENT transformation)

Renamed function symbols to avoid clashes with predefined symbol.

(4) Obligation:

Runtime Complexity Relative TRS:
The TRS R consists of the following rules:

a__a → a__c
a__b → a__c
a__c → e
a__k → l
a__d → m
a__a → a__d
a__b → a__d
a__c → l
a__k → m
a__A → a__h(a__f(a__a), a__f(a__b))
a__h(X, X) → a__g(mark(X), mark(X), a__f(a__k))
a__g(d, X, X) → a__A
a__f(X) → a__z(mark(X), X)
a__z(e, X) → mark(X)
mark(A) → a__A
mark(a) → a__a
mark(b) → a__b
mark(c) → a__c
mark(d) → a__d
mark(k) → a__k
mark(z(X1, X2)) → a__z(mark(X1), X2)
mark(f(X)) → a__f(mark(X))
mark(h(X1, X2)) → a__h(mark(X1), mark(X2))
mark(g(X1, X2, X3)) → a__g(mark(X1), mark(X2), mark(X3))
mark(e) → e
mark(l) → l
mark(m) → m
a__A → A
a__a → a
a__b → b
a__c → c
a__d → d
a__k → k
a__z(X1, X2) → z(X1, X2)
a__f(X) → f(X)
a__h(X1, X2) → h(X1, X2)
a__g(X1, X2, X3) → g(X1, X2, X3)

S is empty.
Rewrite Strategy: FULL

(5) TypeInferenceProof (BOTH BOUNDS(ID, ID) transformation)

Infered types.

(6) Obligation:

TRS:
Rules:
a__a → a__c
a__b → a__c
a__c → e
a__k → l
a__d → m
a__a → a__d
a__b → a__d
a__c → l
a__k → m
a__A → a__h(a__f(a__a), a__f(a__b))
a__h(X, X) → a__g(mark(X), mark(X), a__f(a__k))
a__g(d, X, X) → a__A
a__f(X) → a__z(mark(X), X)
a__z(e, X) → mark(X)
mark(A) → a__A
mark(a) → a__a
mark(b) → a__b
mark(c) → a__c
mark(d) → a__d
mark(k) → a__k
mark(z(X1, X2)) → a__z(mark(X1), X2)
mark(f(X)) → a__f(mark(X))
mark(h(X1, X2)) → a__h(mark(X1), mark(X2))
mark(g(X1, X2, X3)) → a__g(mark(X1), mark(X2), mark(X3))
mark(e) → e
mark(l) → l
mark(m) → m
a__A → A
a__a → a
a__b → b
a__c → c
a__d → d
a__k → k
a__z(X1, X2) → z(X1, X2)
a__f(X) → f(X)
a__h(X1, X2) → h(X1, X2)
a__g(X1, X2, X3) → g(X1, X2, X3)

Types:
a__a :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__c :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__b :: e:l:m:d:A:a:b:c:k:z:f:h:g
e :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__k :: e:l:m:d:A:a:b:c:k:z:f:h:g
l :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__d :: e:l:m:d:A:a:b:c:k:z:f:h:g
m :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__A :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__h :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
a__f :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
a__g :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
mark :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
d :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__z :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
A :: e:l:m:d:A:a:b:c:k:z:f:h:g
a :: e:l:m:d:A:a:b:c:k:z:f:h:g
b :: e:l:m:d:A:a:b:c:k:z:f:h:g
c :: e:l:m:d:A:a:b:c:k:z:f:h:g
k :: e:l:m:d:A:a:b:c:k:z:f:h:g
z :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
f :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
h :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
g :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
hole_e:l:m:d:A:a:b:c:k:z:f:h:g1_0 :: e:l:m:d:A:a:b:c:k:z:f:h:g
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0 :: Nat → e:l:m:d:A:a:b:c:k:z:f:h:g

(7) OrderProof (LOWER BOUND(ID) transformation)

Heuristically decided to analyse the following defined symbols:
a__A, a__h, a__f, a__g, mark, a__z

They will be analysed ascendingly in the following order:
a__A = a__h
a__A = a__f
a__A = a__g
a__A = mark
a__A = a__z
a__h = a__f
a__h = a__g
a__h = mark
a__h = a__z
a__f = a__g
a__f = mark
a__f = a__z
a__g = mark
a__g = a__z
mark = a__z

(8) Obligation:

Generator Equations:
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(0) ⇔ e
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(+(x, 1)) ⇔ z(gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(x), e)

The following defined symbols remain to be analysed:
a__h, a__A, a__f, a__g, mark, a__z

(9) NoRewriteLemmaProof (LOWER BOUND(ID) transformation)

Could not prove a rewrite lemma for the defined symbol a__h.

(10) Obligation:

Generator Equations:
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(0) ⇔ e
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(+(x, 1)) ⇔ z(gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(x), e)

The following defined symbols remain to be analysed:
a__g, a__A, a__f, mark, a__z

(11) NoRewriteLemmaProof (LOWER BOUND(ID) transformation)

Could not prove a rewrite lemma for the defined symbol a__g.

(12) Obligation:

Generator Equations:
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(0) ⇔ e
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(+(x, 1)) ⇔ z(gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(x), e)

The following defined symbols remain to be analysed:
a__A, a__f, mark, a__z

(13) NoRewriteLemmaProof (LOWER BOUND(ID) transformation)

Could not prove a rewrite lemma for the defined symbol a__A.

(14) Obligation:

Generator Equations:
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(0) ⇔ e
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(+(x, 1)) ⇔ z(gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(x), e)

The following defined symbols remain to be analysed:
a__f, mark, a__z

(15) NoRewriteLemmaProof (LOWER BOUND(ID) transformation)

Could not prove a rewrite lemma for the defined symbol a__f.

(16) Obligation:

Generator Equations:
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(0) ⇔ e
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(+(x, 1)) ⇔ z(gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(x), e)

The following defined symbols remain to be analysed:
a__z, mark

(17) NoRewriteLemmaProof (LOWER BOUND(ID) transformation)

Could not prove a rewrite lemma for the defined symbol a__z.

(18) Obligation:

Generator Equations:
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(0) ⇔ e
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(+(x, 1)) ⇔ z(gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(x), e)

The following defined symbols remain to be analysed:
mark

(19) RewriteLemmaProof (LOWER BOUND(ID) transformation)

Proved the following rewrite lemma:
mark(gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(n11571540_0)) → gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(0), rt ∈ Ω(1 + n11571540₀)

Induction Base:
mark(gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(0)) →_R^Ω(1)
e

Induction Step:
mark(gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(+(n11571540_0, 1))) →_R^Ω(1)
a__z(mark(gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(n11571540_0)), e) →_IH
a__z(gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(0), e) →_R^Ω(1)
mark(e) →_R^Ω(1)
e

We have rt ∈ Ω(n¹) and sz ∈ O(n). Thus, we have irc_R ∈ Ω(n).

(20) Complex Obligation (BEST)

(21) Obligation:

Lemmas:
mark(gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(n11571540_0)) → gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(0), rt ∈ Ω(1 + n11571540₀)

Generator Equations:
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(0) ⇔ e
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(+(x, 1)) ⇔ z(gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(x), e)

The following defined symbols remain to be analysed:
a__h, a__A, a__f, a__g, a__z

(22) NoRewriteLemmaProof (LOWER BOUND(ID) transformation)

Could not prove a rewrite lemma for the defined symbol a__h.

(23) Obligation:

Lemmas:
mark(gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(n11571540_0)) → gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(0), rt ∈ Ω(1 + n11571540₀)

Generator Equations:
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(0) ⇔ e
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(+(x, 1)) ⇔ z(gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(x), e)

The following defined symbols remain to be analysed:
a__g, a__A, a__f, a__z

(24) NoRewriteLemmaProof (LOWER BOUND(ID) transformation)

Could not prove a rewrite lemma for the defined symbol a__g.

(25) Obligation:

Lemmas:
mark(gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(n11571540_0)) → gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(0), rt ∈ Ω(1 + n11571540₀)

Generator Equations:
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(0) ⇔ e
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(+(x, 1)) ⇔ z(gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(x), e)

The following defined symbols remain to be analysed:
a__A, a__f, a__z

(26) NoRewriteLemmaProof (LOWER BOUND(ID) transformation)

Could not prove a rewrite lemma for the defined symbol a__A.

(27) Obligation:

Lemmas:
mark(gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(n11571540_0)) → gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(0), rt ∈ Ω(1 + n11571540₀)

Generator Equations:
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(0) ⇔ e
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(+(x, 1)) ⇔ z(gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(x), e)

The following defined symbols remain to be analysed:
a__f, a__z

(28) NoRewriteLemmaProof (LOWER BOUND(ID) transformation)

Could not prove a rewrite lemma for the defined symbol a__f.

(29) Obligation:

Lemmas:
mark(gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(n11571540_0)) → gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(0), rt ∈ Ω(1 + n11571540₀)

Generator Equations:
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(0) ⇔ e
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(+(x, 1)) ⇔ z(gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(x), e)

The following defined symbols remain to be analysed:
a__z

(30) NoRewriteLemmaProof (LOWER BOUND(ID) transformation)

Could not prove a rewrite lemma for the defined symbol a__z.

(31) Obligation:

Lemmas:
mark(gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(n11571540_0)) → gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(0), rt ∈ Ω(1 + n11571540₀)

Generator Equations:
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(0) ⇔ e
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(+(x, 1)) ⇔ z(gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(x), e)

No more defined symbols left to analyse.

(32) LowerBoundsProof (EQUIVALENT transformation)

The lowerbound Ω(n¹) was proven with the following lemma:
mark(gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(n11571540_0)) → gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(0), rt ∈ Ω(1 + n11571540₀)

(33) BOUNDS(n^1, INF)

(34) Obligation:

Lemmas:
mark(gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(n11571540_0)) → gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(0), rt ∈ Ω(1 + n11571540₀)

Generator Equations:
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(0) ⇔ e
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(+(x, 1)) ⇔ z(gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(x), e)

No more defined symbols left to analyse.

(35) LowerBoundsProof (EQUIVALENT transformation)

The lowerbound Ω(n¹) was proven with the following lemma:
mark(gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(n11571540_0)) → gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(0), rt ∈ Ω(1 + n11571540₀)

(0) Obligation:

(1) DecreasingLoopProof (EQUIVALENT transformation)

(2) BOUNDS(2^n, INF)

(3) RenamingProof (EQUIVALENT transformation)

(4) Obligation:

(5) TypeInferenceProof (BOTH BOUNDS(ID, ID) transformation)

(6) Obligation:

(7) OrderProof (LOWER BOUND(ID) transformation)

(8) Obligation:

(9) NoRewriteLemmaProof (LOWER BOUND(ID) transformation)

(10) Obligation:

(11) NoRewriteLemmaProof (LOWER BOUND(ID) transformation)

(12) Obligation:

(13) NoRewriteLemmaProof (LOWER BOUND(ID) transformation)

(14) Obligation:

(15) NoRewriteLemmaProof (LOWER BOUND(ID) transformation)

(16) Obligation:

(17) NoRewriteLemmaProof (LOWER BOUND(ID) transformation)

(18) Obligation:

(19) RewriteLemmaProof (LOWER BOUND(ID) transformation)

(20) Complex Obligation (BEST)

(21) Obligation:

(22) NoRewriteLemmaProof (LOWER BOUND(ID) transformation)

(23) Obligation:

(24) NoRewriteLemmaProof (LOWER BOUND(ID) transformation)

(25) Obligation:

(26) NoRewriteLemmaProof (LOWER BOUND(ID) transformation)

(27) Obligation:

(28) NoRewriteLemmaProof (LOWER BOUND(ID) transformation)

(29) Obligation:

(30) NoRewriteLemmaProof (LOWER BOUND(ID) transformation)

(31) Obligation:

(32) LowerBoundsProof (EQUIVALENT transformation)

(33) BOUNDS(n^1, INF)

(34) Obligation:

(35) LowerBoundsProof (EQUIVALENT transformation)

(36) BOUNDS(n^1, INF)